package leetcode.editor.offer;

// 剑指 Offer 43. 1～n 整数中 1 出现的次数
// https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
class OneNzhengShuZhong1chuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new OneNzhengShuZhong1chuXianDeCiShuLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
    // 把他想象为密码锁
    class Solution {
        public int countDigitOne(int n) {
            int high = n / 10, low = 0, digit = 1, cur = n % 10, res = 0;
            // 高位不为0，cur不为0，才进行循环
            while (high != 0 || cur != 0) {
                if (cur == 0) res += high * digit;
                else if (cur == 1) res += high * digit + low + 1;
                else res += (high + 1) * digit;
                low = cur * digit + low;
                cur = high % 10;
                high /= 10;
                digit *= 10;
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
